package BinaryTree.Easy;

import java.util.ArrayList;

public class LC0872 {
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        ArrayList<Integer> leaves1 = new ArrayList<>(), leaves2 = new ArrayList<>();
        dfs(root1, leaves1);
        dfs(root2, leaves2);

        if (leaves1.size() != leaves2.size()) return false;
        for (int i = 0; i < leaves1.size(); i++) {
            if (!leaves1.get(i).equals(leaves2.get(i))) return false;
        }
        return true;
    }

    private void dfs(TreeNode node, ArrayList<Integer> leaves) {
        if (node.left == null && node.right == null) {
            leaves.add(node.val);
            return;
        }

        if (node.left != null) dfs(node.left, leaves);
        if (node.right != null) dfs(node.right, leaves);
    }
}
